package liangtWorkSpace.sort;

/**
 * @ClassName SelectionSort
 * @Description : 选择排序
 * @Author : LiangT
 * @Date : 2020/8/25 11:32
 */
public class SelectionSort {

    public static void main(String[] args) {
        int[] arr = {1,5,8,4,3,9,7,6,2,0};
        arr  = selection2(arr);
        SortUtils.sout(arr);
    }

    /**
     * 选择排序
     * @param arr
     * @return
     */
    public static int[] selection1(int[] arr){

        for (int i = 0; i < arr.length-1; i++){
            int minPos = i;

            for (int j = i+1; j < arr.length;j++){
                minPos = arr[j] < arr[minPos]?j:minPos;
            }
            if (minPos != i){
                SortUtils.swap(arr,i,minPos);
            }
        }
        return arr;
    }

    /**
     * 双边循环
     * @param arr
     * @return
     */
    public static int[] selection2(int[] arr){

        for (int i = 0; i < arr.length-1; i++){
            int minPos = i;
            int maxPos = arr.length-1-i;
            if ( maxPos < minPos){
                break;
            }
            for (int j = i+1; j < arr.length;j++){
                minPos = arr[j] < arr[minPos]?j:minPos;
            }
            for (int j = arr.length-2-i;j > i;j--){
                maxPos = arr[j] > arr[maxPos]?j:maxPos;
            }
            if (minPos != i){
                SortUtils.swap(arr,i,minPos);
            }
            if (maxPos != arr.length-1-i){
                SortUtils.swap(arr,arr.length-1-i,maxPos);
            }
        }
        return arr;
    }
}
